package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何找出单链表中的倒数第 k 个元素

func main() {
	head := &common.LNode{}
	common.CreateNode1(head, 8)

	fmt.Println("链表：", head)
	fmt.Println("链表倒数第 3 个元素为：", findLastK(head, 3).Data)
}

// 方法一：顺序遍历两遍

// 方法二：快慢指针法
// 如果想要找链表的倒数第 k 个元素，
// 设置两个指针，让其中一个指针比另一个指针先前移 k 步，然后两个指针同时往前移动
func findLastK(head *common.LNode, k int) *common.LNode {
	if head == nil || head.Next == nil {
		return head
	}

	slow := head.Next
	fast := head.Next

	var i int
	for i = 0; i < k && fast != nil; i++ {
		fast = fast.Next
	}

	if i < k {
		return nil
	}

	for fast != nil {
		slow = slow.Next
		fast = fast.Next
	}

	return slow
}
